<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(C卷,200分)- 图像物体的边界（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定一个二维数组M行N列&#xff0c;二维数组里的数字代表图片的像素&#xff0c;为了简化问题&#xff0c;仅包含像素1和5两种像素&#xff0c;每种像素代表一个物体&#xff0c;2个物体相邻的格子为边界&#xff0c;求像素1代表的物体的边界个数。</p> 
<p>像素1代表的物体的边界指与像素5相邻的像素1的格子&#xff0c;边界相邻的属于同一个边界&#xff0c;相邻需要考虑8个方向&#xff08;上&#xff0c;下&#xff0c;左&#xff0c;右&#xff0c;左上&#xff0c;左下&#xff0c;右上&#xff0c;右下&#xff09;。</p> 
<p><strong>其他约束</strong></p> 
<p>地图规格约束为&#xff1a;</p> 
<p>0&lt;M&lt;100<br /> 0&lt;N&lt;100</p> 
<p>1&#xff09;如下图&#xff0c;与像素5的格子相邻的像素1的格子&#xff08;0,0&#xff09;、&#xff08;0,1&#xff09;、&#xff08;0,2&#xff09;、&#xff08;1,0&#xff09;、&#xff08;1,2&#xff09;、&#xff08;2,0&#xff09;、&#xff08;2,1&#xff09;、&#xff08;2,2&#xff09;、&#xff08;4,4&#xff09;、&#xff08;4,5&#xff09;、&#xff08;5,4&#xff09;为边界&#xff0c;另&#xff08;0,0&#xff09;、&#xff08;0,1&#xff09;、&#xff08;0,2&#xff09;、&#xff08;1,0&#xff09;、&#xff08;1,2&#xff09;、&#xff08;2,0&#xff09;、&#xff08;2,1&#xff09;、&#xff08;2,2&#xff09;相邻&#xff0c;为1个边界&#xff0c;&#xff08;4,4&#xff09;、&#xff08;4,5&#xff09;、&#xff08;5,4&#xff09;相邻&#xff0c;为1个边界&#xff0c;所以下图边界个数为2。</p> 
<p><img alt="" height="321" src="https://img-blog.csdnimg.cn/f96fd9573f7f4f228d78d61c5f97a7e9.png" width="358" /></p> 
<p></p> 
<p>2&#xff09;如下图&#xff0c;与像素5的格子相邻的像素1的格子&#xff08;0,0&#xff09;、&#xff08;0,1&#xff09;、&#xff08;0,2&#xff09;、&#xff08;1,0&#xff09;、&#xff08;1,2&#xff09;、&#xff08;2,0&#xff09;、&#xff08;2,1&#xff09;、&#xff08;2,2&#xff09;、&#xff08;3,3&#xff09;、&#xff08;3,4&#xff09;、&#xff08;3,5&#xff09;、&#xff08;4,3&#xff09;、&#xff08;4,5&#xff09;、&#xff08;5,3&#xff09;、&#xff08;5,4&#xff09;、&#xff08;5,5&#xff09;为边界&#xff0c;另这些边界相邻&#xff0c;所以下图边界个数为1。</p> 
<p><img alt="" height="318" src="https://img-blog.csdnimg.cn/c52d48ee453f4ed4b648128b98bb00ca.png" width="359" /></p> 
<p> <strong>注&#xff1a;</strong>&#xff08;2,2&#xff09;、&#xff08;3,3&#xff09;相邻。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行&#xff0c;行数M&#xff0c;列数N</p> 
<p>第二行开始&#xff0c;是M行N列的像素的二维数组&#xff0c;仅包含像素1和5</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>像素1代表的物体的边界个数。</p> 
<p>如果没有边界输出0&#xff08;比如只存在像素1&#xff0c;或者只存在像素5&#xff09;。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;"><code>6 6</code><br /><code>1 1 1 1 1 1</code><br /><code>1 5 1 1 1 1</code><br /><code>1 1 1 1 1 1</code><br /><code>1 1 1 1 1 1</code><br /><code>1 1 1 1 1 1</code><br /><code>1 1 1 1 1 5</code></td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">2</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">参考题目描述部分</td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;"><code>6 6</code><br /><code>1 1 1 1 1 1</code><br /><code>1 5 1 1 1 1</code><br /><code>1 1 1 1 1 1</code><br /><code>1 1 1 1 1 1</code><br /><code>1 1 1 1 5 1</code><br /><code>1 1 1 1 1 1</code></td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">参考题目描述部分</td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题可以使用并查集。</p> 
<p>有几个像素5&#xff0c;我们就可以先假设有几个不相邻的边界。</p> 
<p><img alt="" height="637" src="https://img-blog.csdnimg.cn/9c6a1c995879476e9803b23abe3ff6c8.png" width="735" /></p> 
<p> 而判断两个边界相邻的条件是&#xff1a;两个像素5坐标满足&#xff1a;|x1-x2| &lt;&#61;3 &amp;&amp; |y1-y2| &lt;&#61;3</p> 
<p>即如上图绿色线就是另一个像素5的移动范围边界。</p> 
<p>因此&#xff0c;本题可以转化为求解像素5是否联通的并查集求解。</p> 
<p></p> 
<hr /> 
<p>2023.10.20</p> 
<p>上面思路其实存在一定偏差。</p> 
<p>因为本题要求解的是&#xff1a;像素1代表的物体的边界个数。我们可以看一个例子&#xff1a;</p> 
<p><img alt="" height="224" src="https://img-blog.csdnimg.cn/f39de616c7244247b0befa528448f369.png" width="217" /></p> 
<p>上图所示&#xff0c;应该存在几个边界呢&#xff1f;</p> 
<p>如果按照前面思路&#xff0c;则只有1个边界。前面思路其实是以像素5为核心&#xff0c;将像素5周围的像素1统一视为一个边界&#xff0c;但是这是不符合题意的&#xff0c;因为题目要求说&#xff1a;</p> 
<blockquote> 
 <p>像素1代表的物体的边界指<span style="color:#fe2c24;">与像素5相邻的像素1的格子&#xff0c;<strong>边界相邻的属于同一个边界</strong></span></p> 
</blockquote> 
<p>而上面图示中&#xff0c;两个像素1格子是不相邻的&#xff0c;因此不能算同一边界。</p> 
<p></p> 
<p>我的解题思路如下&#xff1a;</p> 
<p>首先&#xff0c;遍历矩阵&#xff0c;将<strong>所有像素5</strong>相邻的像素1&#xff08;边界&#xff09;坐标都取出来。</p> 
<p>然后&#xff0c;利用并查集&#xff0c;对这些边界像素1格子进行合并&#xff0c;合并规则是&#xff1a;</p> 
<blockquote> 
 <p>两个格子的横向、纵向距离均小于等于1&#xff0c;即为相邻&#xff0c;即可合并。</p> 
</blockquote> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; sc.nextInt();
    int n &#61; sc.nextInt();

    int[][] matrix &#61; new int[m][n];
    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        matrix[i][j] &#61; sc.nextInt();
      }
    }

    System.out.println(getResult(matrix, m, n));
  }

  public static int getResult(int[][] matrix, int m, int n) {
    // 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量
    int[][] offsets &#61; {<!-- -->{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

    // 记录所有边界位置
    HashSet&lt;Integer&gt; brands &#61; new HashSet&lt;&gt;();

    for (int i &#61; 0; i &lt; m; i&#43;&#43;) {
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        // 如果当前点是像素5
        if (matrix[i][j] &#61;&#61; 5) {

          // 遍历像素5的相邻位置
          for (int[] offset : offsets) {
            int newI &#61; i &#43; offset[0];
            int newJ &#61; j &#43; offset[1];

            // 如果该位置不越界&#xff0c;且为像素1&#xff0c;则是边界
            if (newI &gt;&#61; 0 &amp;&amp; newI &lt; m &amp;&amp; newJ &gt;&#61; 0 &amp;&amp; newJ &lt; n &amp;&amp; matrix[newI][newJ] &#61;&#61; 1) {
              brands.add(newI * n &#43; newJ);
            }
          }
        }
      }
    }

    ArrayList&lt;Integer&gt; brands_list &#61; new ArrayList&lt;&gt;(brands);
    int k &#61; brands_list.size();

    // 使用并查集&#xff0c;对所有边界位置进行合并
    UnionFindSet ufs &#61; new UnionFindSet(k);

    for (int i &#61; 0; i &lt; k; i&#43;&#43;) {
      int x1 &#61; brands_list.get(i) / n;
      int y1 &#61; brands_list.get(i) % n;

      for (int j &#61; i &#43; 1; j &lt; k; j&#43;&#43;) {
        int x2 &#61; brands_list.get(j) / n;
        int y2 &#61; brands_list.get(j) % n;

        // 如果两个边界像素1的位置 横向、纵向距离均小于1&#xff0c;则相邻&#xff0c;可以进行合并
        if (Math.abs(x1 - x2) &lt;&#61; 1 &amp;&amp; Math.abs(y1 - y2) &lt;&#61; 1) {
          ufs.union(i, j);
        }
      }
    }

    return ufs.count;
  }
}

class UnionFindSet {
  int[] fa;
  int count;

  public UnionFindSet(int n) {
    this.count &#61; n;
    this.fa &#61; new int[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) this.fa[i] &#61; i;
  }

  public int find(int x) {
    if (x !&#61; this.fa[x]) {
      return (this.fa[x] &#61; this.find(this.fa[x]));
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa &#61; this.find(x);
    int y_fa &#61; this.find(y);

    if (x_fa !&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
      this.count--;
    }
  }
}
</code></pre> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JS算法源码</h4> 
<pre><code class="language-javascript">const rl &#61; require(&#34;readline&#34;).createInterface({ input: process.stdin });
var iter &#61; rl[Symbol.asyncIterator]();
const readline &#61; async () &#61;&gt; (await iter.next()).value;

void (async function () {
  const [m, n] &#61; (await readline()).split(&#34; &#34;).map(Number);

  const matrix &#61; [];
  for (let i &#61; 0; i &lt; m; i&#43;&#43;) {
    matrix.push((await readline()).split(&#34; &#34;).map(Number));
  }

  console.log(getBrandCount(matrix, m, n));
})();

function getBrandCount(matrix, m, n) {
  // 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量
  const offsets &#61; [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
    [-1, -1],
    [-1, 1],
    [1, -1],
    [1, 1],
  ];

  // 记录所有边界位置
  const brands &#61; new Set();

  for (let i &#61; 0; i &lt; m; i&#43;&#43;) {
    for (let j &#61; 0; j &lt; n; j&#43;&#43;) {
      // 如果当前点是像素5
      if (matrix[i][j] &#61;&#61;&#61; 5) {
        // 遍历像素5的相邻位置
        for (let offset of offsets) {
          const newI &#61; i &#43; offset[0];
          const newJ &#61; j &#43; offset[1];

          // 如果该位置不越界&#xff0c;且为像素1&#xff0c;则是边界
          if (
            newI &gt;&#61; 0 &amp;&amp;
            newI &lt; m &amp;&amp;
            newJ &gt;&#61; 0 &amp;&amp;
            newJ &lt; n &amp;&amp;
            matrix[newI][newJ] &#61;&#61; 1
          ) {
            brands.add(newI * n &#43; newJ);
          }
        }
      }
    }
  }

  const brands_list &#61; [...brands];
  const k &#61; brands_list.length;

  // 使用并查集&#xff0c;对所有边界位置进行合并
  const ufs &#61; new UnionFindSet(k);

  for (let i &#61; 0; i &lt; k; i&#43;&#43;) {
    const x1 &#61; Math.floor(brands_list[i] / n);
    const y1 &#61; brands_list[i] % n;

    for (let j &#61; i &#43; 1; j &lt; k; j&#43;&#43;) {
      const x2 &#61; Math.floor(brands_list[j] / n);
      const y2 &#61; brands_list[j] % n;

      // 如果两个边界像素1的位置 横向、纵向距离均小于1&#xff0c;则相邻&#xff0c;可以进行合并
      if (Math.abs(x1 - x2) &lt;&#61; 1 &amp;&amp; Math.abs(y1 - y2) &lt;&#61; 1) {
        ufs.union(i, j);
      }
    }
  }

  return ufs.count;
}

class UnionFindSet {
  constructor(n) {
    this.fa &#61; [];
    for (let i &#61; 0; i &lt; n; i&#43;&#43;) {
      this.fa.push(i);
    }
    this.count &#61; n;
  }

  find(x) {
    if (x !&#61;&#61; this.fa[x]) {
      this.fa[x] &#61; this.find(this.fa[x]);
      return this.fa[x];
    }
    return x;
  }

  union(x, y) {
    let x_fa &#61; this.find(x);
    let y_fa &#61; this.find(y);
    if (x_fa !&#61;&#61; y_fa) {
      this.fa[y_fa] &#61; x_fa;
      this.count--;
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
m, n &#61; map(int, input().split())
matrix &#61; [list(map(int, input().split())) for _ in range(m)]


# 并查集
class UnionFindSet:
    def __init__(self, n):
        self.fa &#61; [idx for idx in range(n)]
        self.count &#61; n

    def find(self, x):
        if x !&#61; self.fa[x]:
            self.fa[x] &#61; self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa &#61; self.find(x)
        y_fa &#61; self.find(y)

        if x_fa !&#61; y_fa:
            self.fa[y_fa] &#61; x_fa
            self.count -&#61; 1


# 算法入口
def getResult():
    # 上、下、左、右、左上、左下、右上、右下的横坐标、纵坐标偏移量
    offsets &#61; ((-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1))

    # 记录所有边界位置
    brands &#61; set()

    for i in range(m):
        for j in range(n):
            # 如果当前点是像素5
            if matrix[i][j] &#61;&#61; 5:
                # 遍历像素5的相邻位置
                for offset in offsets:
                    newI &#61; i &#43; offset[0]
                    newJ &#61; j &#43; offset[1]

                    # 如果该位置不越界&#xff0c;且为像素1&#xff0c;则是边界
                    if m &gt; newI &gt;&#61; 0 and n &gt; newJ &gt;&#61; 0 and matrix[newI][newJ] &#61;&#61; 1:
                        brands.add(newI * n &#43; newJ)

    brands_list &#61; list(brands)
    k &#61; len(brands_list)

    # 使用并查集&#xff0c;对所有边界位置进行合并
    ufs &#61; UnionFindSet(k)

    for i in range(k):
        x1 &#61; brands_list[i] // n
        y1 &#61; brands_list[i] % n

        for j in range(i &#43; 1, k):
            x2 &#61; brands_list[j] // n
            y2 &#61; brands_list[j] % n

            # 如果两个边界像素1的位置 横向、纵向距离均小于1&#xff0c;则相邻&#xff0c;可以进行合并
            if abs(x1 - x2) &lt;&#61; 1 and abs(y1 - y2) &lt;&#61; 1:
                ufs.union(i, j)

    return ufs.count


# 算法调用
print(getResult())
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>